#include <iostream>
#include <queue>

using std::cout;
using std::endl;
using std::priority_queue;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
 
class Solution {
public:
    void foreach(TreeNode *node, priority_queue<int> &que, int &k)
    {
        if(!node) return;
        k--;
        if(k >= 0) que.push(node->val);
        else{
            if(que.top() > node->val){
                que.pop();
                que.push(node->val);
            }
        }
        foreach(node->left, que, k);
        foreach(node->right, que, k);
    }

    int kthSmallest(TreeNode* root, int k) {
        priority_queue<int> que;
        foreach(root, que, k);
        return que.top();
    }
};

void test1()
{
    Solution sol;
    TreeNode *root = new TreeNode(3);
    root->left = new TreeNode(1);
    root->right = new TreeNode(4);
    root->left->right = new TreeNode(2);

    cout << sol.kthSmallest(root, 3) << endl;
}

int main(int argc, char const *argv[])
{
    test1();
    return 0;
}
